package luogu;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
class A5318{
    static int n;
    static int m;
    static int[] h;
    static int[] e;
    static int[] ne;
    static int idx=1;
    static int[] vis1;
    static int[] vis2;
    public static void main(String[] args){

        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        h=new int[n+1];
        e=new int[m+5];
        ne=new int[m+5];
        vis1=new int[n+1];
        vis2=new int[n+1];
        for(int i=1;i<=m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            add(a,b);
        }
        //将1标记为走过了
        System.out.print(1+" ");
        vis1[1]=1;
        dfs(1);
        System.out.println();
        bfs(1);
    }
    static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    static void bfs(int a) {

        int[] q = new int[n + 10];
        int hh = 0, tt = -1;
        vis2[a] = 1;
        q[++tt] = a;//标记且加入队列
        //输出
        System.out.print(a + " ");
        while (hh <= tt) {
            //队列不为空
            int t = q[hh++];

            ArrayList<Integer> neighbors = new ArrayList<>();
            for (int edge = h[t]; edge != 0; edge = ne[edge]) {
                neighbors.add(e[edge]);
            }
            Collections.sort(neighbors); // 按从小到大排序
            for (int cur : neighbors) {
                if (vis2[cur] == 0) {
                    System.out.print(cur + " ");
                    vis2[cur] = 1; // 标记走过了
                    q[++tt] = cur; // 加入队列
                }
            }
        }
    }
    static void dfs(int a){
        ArrayList<Integer> list=new ArrayList();
        //将a指向的点根据大小排序
        for(int edge=h[a];edge!=0;edge=ne[edge]){
            int cur=e[edge];
            list.add(cur);
            }
        Collections.sort(list); // 按从小到大排序
            for (Integer i : list) {
                if(vis1[i]==0)
                {
                    System.out.print(i+" ");
                vis1[i]=1;
                dfs(i);
                }

            }


        }

    }
